A significant amount of effort has been expended in the development of high data rate digital communication. Such communication technologies have brought about wireless local area networks, such as those defined in IEEE802.11a and HIPERLAN/2.
Reducing the computational complexity in the receivers of such a network would be beneficial for implementation of such systems because of the limited resources available in many low cost commercial devices.
FIG. 1 is a block diagram of a communication system wherein the present invention can be applied. The transmitter part including encoder 2, interleaver 10, bit mapper 12, modulator 14 and transmitter 16 is in accordance with the HIPERLAN/2 and 802.11a standards. In both of these standards different quadrature amplitude modulation (QAM) formats are used, such as bi-phase shift key (BPSK), quadrature phase shift key (QPSK), 16 QAM and 64 QAM.
In general a first user (which may be human or machine) wishes to transmit a data stream to a second user. The bits in the data stream are firstly convolutionally encoded by an encoder 2 to provide forward error correction. Schemes for convolutional encoding are well known to the person skilled in the art and hence only a brief description is required here. In general convolutional encoding is performed by shifting the data through a chain of delay elements usually implemented as a shift register. In the case of the HIPERLAN/2 and 802.11a standards the convolutional code has a rate ½ and a constraint length of seven.
The chain, as shown in FIG. 2, includes taps at various points. The tapped signals are summed together by summers 4 and 6 which are implemented as modulo 2 adders, which are often physically realised as a cascade of exclusive—OR gates.
The arrangement shown in FIG. 2 has six delay elements T and data can also be tapped off at the input to the first element. The encoder shown has, in effect, seven snapshots of the input string and is therefore described as having a constraint length of 7.
The encoder 2 produces two data outputs Y1 and Y2 in accordance with the series of connections and taps that are formed within it. Working from the input to the output, the first output is represented by the first, the third, fourth, sixth and seventh taps, or 1011011. The second output Y2 is represented by 1111001. Thus the code generator for this encoder is [133, 171] in octal format. Because the convolutional code has rate ½ the data entering the encoder 2 is a scalar bit stream, while the data leaving the encoder is a stream of binary bit pairs. The data outputs of the encoder 2 are sent to a bit interleaver 10 which spreads the bits so that potential errors caused by channel degradation are seen as independent at the receiver. The interleaved bits are then converted into quadrature-amplitude modulated (QAM) signals by QAM mapper 12 having Gray code labelling.
In other words, bit interleaver 10 and bit mapper 12 cause sequences of 2 m bits to be assigned to one of the M=22m points in the QAM constellation. The mapping is performed as a Gray coding such that sequences of bits associated with adjacent symbols only differ by one bit.
An exemplary 16-QAM constellation, where m=2, based on the foregoing, is shown in FIG. 3.
Bit mapper 12 feeds the complex (real and imaginary parts) signals to orthogonal frequency division multiplexing (OFDM) modulator 14. OFDM is a multi-carrier modulation process that subdivides the frequency spectrum that it uses into a plurality of channels. The process gives good performance over a dispersive transmission path. The data stream is split into Nsd lower rate data streams that are transmitted over Nsd sub-carriers. The symbol duration increases for the parallel sub-carriers and hence the transmission scheme is more robust in the presence of multi-path interference.
Finally the signal is transmitted by a radio frequency transmitter 16 such that the radio signal propagates via a transmission channel 18 (that in many instances tends to be dispersive and noisy) to a receiver 20. Receiver 20 includes an automatic gain control (AGC) circuit to assure that the receiver average output amplitude is normalised.
Consider the performance of a generic ith sub-carrier used in the OFDM process. The ith channel carries a series of QAM symbols. If we consider just one of these symbols, thenα[i]=αI[i]+jαQ[i]  (1)Where                α[i] represents the symbol in the ith sub-carrier        αI[i] represents the real component of symbol α[i]        αQ[i] represents the imaginary component of symbol α[i], and,        j represents the imaginary operator, i.e., √{square root over (−1)}.        
Each symbol represents a convolutionally encoded bit sequence given by {bI,1; bI,2 . . . ; bI,m; bQ,1; bQ,2; . . . bQ,m}, as shown in FIG. 3 for a 16 QAM constellation.
The output of the receiver 20 drives OFDM demodulator 22 whose output is fed to an analog to digital converter (not shown) that drives an equalizer and soft-output QAM demapper 24. Assuming that the cyclic prefix, introduced by the OFDM modulator 14, completely eliminates ISI (Inter OFDM Symbol Interference) and ICI (Inter Channel Interference) and that the channel estimate is error free, the received equalised signal in the ith sub-carrier is given by:y[i]=r[i]/Gch(i)=a[i]+w[i]/Gch(i)  (2)Where    r[i] is the received signal before equalization at the output of the OFDM demodulator 22 in the ith sub-carrier,    Gch(i) is the Channel Frequency Response (CFR) coefficient (a complex number) in the ith sub-carrier, and    w[i] is the complex Additive White Gaussian Noise (AWGN).
The de-mapper 24 also receives information from a channel state information (CSI) estimator 26, responsive to an output of demodulator 22. The CSI estimator 26 attempts to deduce, i.e., estimate, the effect of the transmission path of channel 18 on the signal propagating in the channel.
In broad terms channel 18 both scales the QAM signals and rotates them in phase, i.e., the QAM constellation gets rotated. The CSI estimator 26 attempts to estimate the effect of the channel 18 on the symbol. The CSI estimator can work on the assumption that channel 18 is slowly time variant. However, the physical transmission scheme includes “preambles” which contain known sequences of symbols that can be used to estimate the status of channel 18. Thus estimator 26 derives individual phase and modulus estimates for each channel 18 by identifying the preamble.
The output of the demapper 24 drives de-interleaver 28, which in turn drives a convolutional decoder 30, that typically decodes based on the Viterbi algorithm. The Viterbi algorithm of decoder 30 searches the possible code words of the convolutional code and detects the one that is most likely to have generated the received sequence. The search procedure of decoder 30 steps through the code trellis and for each path along the trellis computes a metric which quantifies the discrepancy between the received sequence and the possible coded sequence. If the information associated with bits fed into the decoder is hard (i.e., binary, a sequence of −1's and 1's) the decoder 30 is called a hard decision decoder. Alternatively, if the information is soft, consisting of a hard decision (the sign, i.e., polarity) and a confidence level, or reliability (the magnitude), that represents how much confidence there should be in the hard-decision, the decoder 30 is called a soft-decision decoder. It is well known that soft decision Viterbi decoding can give significant gain over hard decoding at the expense, however, of a greater computational complexity. In order to implement a soft-decision Viterbi decoder, the demapper 24, which precedes the Viterbi decoder 30, needs to deliver soft information associated with the bits.
Soft decision demapping for bit interleaved coded modulation (BICM) signals with BPSK or QPSK modulations is straightforward as the soft bit information, before being weighted by the Channel State Information (CSI), is simply given by the received signals for BPSK and by their quadrature-phase and quadrature components for QPSK. Therefore in the following discussion, consideration is given to the higher modulation formats, for which soft detection requires much more computational effort.
In the literature, two different approaches can be found to calculate the soft information for BICM signals, with multi-level modulations.
One prior art mechanism for bit interleaved coded modulation (BICM) schemes was disclosed by E. Zehavi, “8-PSK Trellis Codes for a Rayleigh Channel” IEEE Trans on Comm, Vol 40, pp 873-884, May 1992. The process starts by calculating sub-optimal bit metrics that are then used inside a Viterbi decoder for path metric computation.
For each bit bI,K and each bit bQ,K (where I and Q represent in-phase and quadrature parts, respectively, and K represents an index of the bit associated with the symbol, where K is an integer in the range 1≦K≦m) the QAM constellation is split into two partitions of complex symbols.
These partitions are                SI,K(0) having symbols with a 0 in position I, K.        SI,K(1) having symbols with a 1 in the position I, K.        SQ,K(0) having symbols with a 0 in position Q, K.        SQ,K(1) having symbols with a 1 in position Q, K.        
The bit metrics are given by
                                                                        M                C                            ⁡                              (                                  b                                      I                    ,                    K                                                  )                                      =                                                                                                                                                  G                        CH                                            ⁡                                              (                        i                        )                                                                                                  2                                ·                min                            ⁢                                                                                                            y                      ⁡                                              [                        i                        ]                                                              -                    a                                                                    2                                              ,                      c            =                          0              ,              1                                      ⁢                                  ⁢                                  ⁢                  α          ∈                      S                          I              ,              K                                      (              c              )                                                          (        3        )            
Finally the metrics are de-interleaved by a de-interleaver 28 and provided as an input to a Viterbi decoder 30.
The Viterbi decoder 30 works according to a well known algorithm which need not be described in detail here. However various web sites give tutorials in Viterbi decoding, such as http://pweb.netcom.com/˜chip.f/viterbi/algrthms2.html.
The convolutional encoder 2 functions as a state machine and the Viterbi decoder 30 is furnished with a state map of the state machine showing which state to state transitions are allowed and which ones are disallowed.
In the second prior art approach, the QAM symbols are first demodulated by a soft output de-mapper and passed to a soft-input Viterbi decoder; see M. Speth et al, “Low Complexity Space-Frequency MLSE for Multi-User COFDM”, IEEE GLOBECOM '99, pp 2395-99, December 1999.
In this approach the process seeks to de-map the received signal into soft bits which have the same sign as that provided by a hard decoder and whose magnitude indicates the reliability of the decision.
The soft bit information assigned to bit bI,K can be shown to be given by the log-likelihood ratio (LLR) of the hard decision on bI,K (see R. Pyndiah et al “Near Optimum Decoding of Product Codes”, IEEE GLOBECOM 94, pp 339-43, November-December, 1994) and can be approximated by
                                          LLR            ⁡                          (                              b                                  I                  ,                  K                                            )                                =                                                                                                                                G                      CH                                        ⁡                                          (                      i                      )                                                        4                                                            2                        ⁢                          {                                                min                  ⁢                                                                                                                                    y                          ⁡                                                      [                            i                            ]                                                                          -                        α                                                                                    2                                                  -                                  min                  ⁢                                                                                                                                    y                          ⁡                                                      [                            i                            ]                                                                          -                        α                                                                                    2                                                              }                                      ⁢                                  ⁢                                  ⁢                  {                                          ⁢                      α            ∈                                          S                                  I                  ,                  K                                                  (                  0                  )                                            ⁢                                                          ⁢              α                        ∈                          S                              I                ,                K                                            (                1                )                                              ⁢                                          }                                    (        4        )            LLR(bI,K)Δ|GCH(i)|2·DI,K  (5)
We define
      S          I      ,      K              ′      ⁡              (        c        )              ⁢      =    Δ    ⁢      ℛ    ⁢          {              S                  I          ,          K                          (          c          )                    }      as the subset containing the real parts of the complex symbols of subset SI,K(c), for c=0.1. It can be shown that equation (4) can be rewritten in a simpler form,
                                          LLR            ⁡                          (                              b                                  I                  ,                  K                                            )                                =                                                                                                                                G                      CH                                        ⁡                                          (                      i                      )                                                        4                                                            2                        ⁢                          {                                                                    min                    ⁡                                          (                                                                                                    y                            I                                                    ⁡                                                      [                            i                            ]                                                                          -                                                  α                          I                                                                    )                                                        2                                -                                                      min                    ⁡                                          (                                                                        y                          I                                                -                                                  α                          I                                                                    )                                                        2                                            }                                      ⁢                                  ⁢                                  ⁢                  {                                          ⁢                                    α              I                        ∈                                          S                                  I                  ,                  K                                                  ′                  ⁡                                      (                    0                    )                                                              ⁢                                                          ⁢                              α                I                            ⁢                              S                                  I                  ,                  K                                                  ′                  ⁡                                      (                    1                    )                                                                                ⁢                                          }                                    (        6        )            
Where the two minima are now taken over real values instead of complex symbols.
If this is, for convenience, explicitly evaluated for the 16 QAM symbols we have
                                                                        D                                  I                  ,                  1                                            =                                                                                                                  y                        I                                            ⁡                                              [                        i                        ]                                                                                                                                                                                                                              y                            1                                                    ⁡                                                      [                            i                            ]                                                                                                                      ≤                      2                                                                                                                                  2                      ⁢                                              (                                                                                                            y                              I                                                        ⁡                                                          [                              i                              ]                                                                                -                          1                                                )                                                                                                                                                                          y                          I                                                ⁡                                                  [                          i                          ]                                                                    >                      2                                                                                                                                  2                      ⁢                                              (                                                                                                            y                              I                                                        ⁡                                                          [                              i                              ]                                                                                +                          1                                                )                                                                                                                                                                          y                          I                                                ⁡                                                  [                          i                          ]                                                                    <                      2                                                                                                                                                              D                                  I                  ,                  2                                            =                                                -                                                                                                        y                        I                                            ⁡                                              [                        i                        ]                                                                                                                +                2.                                                                        (        7        )            
Equivalent expressions hold for the quadrature components with “I” replaced by “Q”.
It has been demonstrated in F. Tosato and P. Bisaglia “Simplified Soft-Output Demapper for Binary Interleaved COFDM with Application to HIPERLAN/2”, IEEE ICC 2002, April-May, 2002, that using the approximate bit metrics MC(bI,K) in equation 3 for path metric calculation inside the Viterbi algorithm is equivalent to demodulating the signals into soft bit values according to equation 6 and then employing a soft Viterbi algorithm for decoding.
The formula for calculating the log likelihood ratio in equation 6 can be further approximated by calculating |DI,K| (or indeed |DQ,K|) as the distance of the received equalised signal y[i] from the nearest partition boundary within the partitioned QAM space and assigning DI,K (or DQ,K as appropriate) the sign “+” or “−” according to the partition in which y[i] falls. The magnitude (i.e., absolute value) is a measure of distance of the received symbol from the decision boundary.
FIG. 4a is an illustration of the decision boundaries B1 to B4 for 16 QAM modulation and FIGS. 4b to 4e are illustrations of the resulting partitions in 16 QAM space.
FIG. 4b indicates the partitions SI,1(0) and SI,1(1) in the I axis direction for the left most bits in the symbols of FIG. 4a, i.e., for bits bI,1. Partition SI,1(0) thus includes symbols having left most bits having 0 values while partition SI,1(1) includes symbols having left most bits having 1 values. Each of partitions SI,1(0) and SI,1(1) has the same area and includes two columns of four symbols, on opposite sides of the Q axis.
FIG. 4c indicates the partitions SI,2(0) and SI,2(1) in the I axis direction for the second to the left bits in the symbols of FIG. 4a, i.e., for bits bI,2. Partition SI,2(0) includes two separate parts and includes symbols having second to the left bits with 0 values while partition SI,2(1) includes symbols having second to the left bits with 1 values. Partition SI,2(1) is bisected by the Q axis and includes two columns of four symbols on opposite sides of the Q axis. One of partitions SI,2(0) is on the right side of partition SI,2(1) while the other SI,2(0) partition is on the left side of partition SI,2(1). Each of partitions SI,2(0) includes a single column of four symbols.
FIG. 4d indicates the partitions SQ,1(0) and SQ,1(1) in the Q axis direction for the third to the left bits in the symbols of FIG. 4a, i.e., for bits bQ,1. Partition SQ,1(0) includes symbols having third to the left bits with 0 values while partition S(Q),1(1) includes symbols having third to the left bits with 0 values. Each of partitions SQ,1(0) and SQ,1(1) has the same area and includes two rows of four symbols on opposite sides of the I axis.
FIG. 4e indicates the partitions SQ,2(0) and SQ,2(1) in the Q axis direction for the right most bits in the symbols of FIG. 4a, i.e., for bits bQ,2. Partition SQ,2(0) has two separate parts and includes symbols with the right most bit having 0 values, while SQ,2(1) includes symbols with the right most bit having 1 values. Partition SQ,2(1) is bisected by the I axis and includes two rows of four symbols. One of partitions SQ,2(0) is above partition SQ,2(1), while the other partition SQ,2(0) is below partition SQ,2(1). Each of partitions SQ,2(0) includes a single row of four symbols.
The partitions of FIGS. 4b-4e enable the bit values of a symbol of a sixteen symbol QAM constellation to be determined. The 16 QAM constellation is used by way of an example. However the present invention can be applied to higher order constellations in a similar way.
Furthermore by letting dI,K and dQ,K denote half the distance between the partition boundaries B2 and B4 relative to bit bI,K and, bQ,K respectively, then for the 16 and 64 QAM constellations with Gray mapping used in IEEE802.11a and HIPERLAN/2, it can be shown that
                              D                      I            ,            K                          ≅                                                                                                  y                    I                                    ⁡                                      [                    i                    ]                                                  ,                                                                    K                =                1                                                                                                                              -                                                                                        D                                                  I                          ,                                                      K                            -                            1                                                                                                                                                      +                                      d                                          I                      ,                      K                                                                      ,                                                                    K                >                1                                                                        (        8        )            
In terms of computational complexity the prior art system of decoding the symbols, even with all of the simplifications and approximations invoked, is computationally complex.
To illustrate this complexity, consider the case of a burst transmission. In a burst transmission the channel 18 can be assumed to be time-invariant for the duration of the burst. Thus channel state estimation need only be performed once by the receiver at the beginning of each burst.
If we denote Nb the number of bits coded in the data burst and Nsd the number of sub-carriers (Nb>>NSD) then LLR calculation using the formulae:LLR(bI,K)=|Gch(i)|2·DI,K LLR(bQ,K)=|Gch(i)|2·DQ,K  (9)requires one real multiplication per coded bit, plus computation of Nsd squared modulus of complex values per physical data burst, which is equivalent to 2Nsd real multiplications.
Thus, the approximate LLR calculation requires (Nb+2NSD) real multiplications.